package org.basis.algorithm.search;

/**
 * 二分搜索模板以及常用题型
 *
 * @author wenpan 2024/03/02 10:57
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 5, 6, 7, 8, 9};
        final int target = 5;
        int index = simpleSearch(nums, target);
        System.out.println("简单二分法结果：" + index);
        nums = new int[]{1, 2, 3, 3, 3, 3, 5, 5, 5, 5, 5, 6, 7, 8, 9};
        index = leftBoundSearch(nums, target);
        System.out.println("寻找最左边界结果: " + index);
        index = rightBoundSearch(nums, target);
        System.out.println("寻找最右边界结果: " + index);
    }

    /**
     * 简单的二分搜索，给定一个数target和一个有序数组nums(数组里没有重复元素)，如果target在Nums里则返回数组下标，反之则返回-1
     * 这就是最简单二分搜索的
     */
    public static int simpleSearch(int[] nums, int target) {
        if (nums == null) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 给定一个升序数组nums，数组内可能会有重复数字，给定一个数target，判断如果target在nums中，则返回target在Nums里的最左侧位置的下标
     * 反之则返回-1
     * 直接套二分搜索的模板，当然你也可以用简单二分法找到target元素后再继续向左探测，直到遇到第一个不等于target的元素为止，这样的话复杂度会高些
     */
    public static int leftBoundSearch(int[] nums, int target) {
        if (nums == null) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // 因为要查找最左边界，所以遇到nums[mid] = target的情况不要直接返回，而是继续向左移动右边界
                right = mid - 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }

        // 判定
        // 左指针已经走到了右侧边界仍然未找到相等的数，那么说明没有相等的
        if (left >= nums.length) {
            return -1;
        }

        // 结果返回，这里由于是查找最左边界，所以用nums[left]来判定
        return nums[left] == target ? left : -1;
    }

    /**
     * 给定一个升序数组nums，数组内可能会有重复数字，给定一个数target，判断如果target在nums中，则返回target在Nums里的最右侧位置的下标
     * 反之则返回-1
     * 直接套二分搜索的模板，当然你也可以用简单二分法找到target元素后再继续向右探测，直到遇到第一个不等于target的元素为止，这样的话复杂度会高些
     */
    public static int rightBoundSearch(int[] nums, int target) {
        if (nums == null) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // 遇到相等的了，不要着急返回，而是继续移动左边界向右探测
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        // 判断
        if (right < 0) {
            // 特殊情况，右指针都走到最左边界了还是没有找到等于target的值
            return -1;
        }
        return nums[right] == target ? right : -1;
    }

}
